Чому обробка відсортованого масиву відбувається швидше, ніж обробка невідсортованого масиву?

Ви жертва невдалого прогнозування гілок.
Що таке передбачення галузі?
Розглянемо залізничний вузол:
Зображення Mecanismo, через Wikimedia Commons. Використовується за ліцензією CC-By-SA 3.0.
Тепер для аргументації, припустимо, це було у 1800-х роках - до міжміського або радіозв’язку.
Ви є оператором вузла, і ви чуєте, як підходить поїзд. Ви не уявляєте, яким шляхом він повинен йти. Ви зупиняєте поїзд, щоб запитати машиніста, в якому напрямку вони хочуть. І тоді ви встановлюєте перемикач відповідним чином.
Потяги важкі та мають велику інерцію. Тому їм потрібно вічно запускатись і гальмувати.
Чи є кращий спосіб? Ти здогадуєшся, в якому напрямку буде йти поїзд!
Якщо ви правильно вгадали, це продовжується далі.
Якщо ви вгадали неправильно, капітан зупиниться, зробить резервну копію і закричить на вас, щоб ви натиснули перемикач. Тоді він може перезапустити інший шлях.
Якщо кожного разу вгадувати правильно, поїзду ніколи не доведеться зупинятися. Якщо ви занадто часто вгадуєте неправильно, поїзд витратить багато часу на зупинку, резервне копіювання та перезапуск.
Розглянемо твердження if: На рівні процесора це інструкція гілки:
Ви переробник і бачите гілку. Ви не уявляєте, яким шляхом він піде далі. Що ти робиш? Ви зупиняєте виконання і чекаєте, поки не закінчаться попередні інструкції. Потім ви продовжуєте правильний шлях.
Сучасні процесори складні і мають довгі трубопроводи. Тому їм потрібно вічно, щоб «зігрітися» і «сповільнитись».
Чи є кращий спосіб? Ти здогадуєшся, в якому напрямку піде гілка!
Якщо ви правильно вгадали, ви продовжуєте виконувати.
Якщо ви неправильно вгадали, вам потрібно промити трубопровід і повернутися назад до гілки. Тоді ви можете перезапустити інший шлях.
Якщо кожного разу вгадувати правильно, страту ніколи не доведеться зупиняти. Якщо ви занадто часто вгадуєте неправильно, ви витрачаєте багато часу на затримку, відкат і перезапуск.
Це передбачення галузі. Я визнаю, що це не найкраща аналогія, оскільки поїзд міг би просто сигналізувати про напрямок прапором. Але в комп’ютерах процесор до останнього моменту не знає, в якому напрямку буде рухатися гілка.
То як би ви стратегічно вгадали, щоб мінімізувати кількість разів, коли поїзд повинен повертатись назад і спускатися іншим шляхом? Ви подивіться на минулу історію! Якщо поїзд рухається ліворуч 99% часу, то ви здогадуєтесь ліворуч. Якщо воно чергується, то ви чергуєте свої здогадки. Якщо воно йде в один бік кожні три рази, ви здогадуєтеся те саме ...
Іншими словами, ви намагаєтеся визначити зразок і слідувати йому. Більш-менш працюють передбачувачі галузей.
У більшості додатків є добре розвинені гілки. Отже, сучасні прогнозування галузей, як правило, досягають> 90% показників звернень. Але зіткнувшись з непередбачуваними гілками без впізнаваних закономірностей, прогнози гілок практично марні.
Подальше читання: стаття "Віщувач філій" у Вікіпедії.
Як натякали згори, винуватцем цього є твердження if:
якщо (дані [c]> = 128)
сума + = дані [c];
Зверніть увагу, що дані розподіляються рівномірно між 0 і 255. Коли дані відсортовані, приблизно перша половина ітерацій не буде вводити оператор if. Після цього всі вони будуть вводити оператор if.
Це дуже доброзичливо для передбачувача гілки, оскільки гілка багато разів послідовно рухається в одному напрямку. Навіть простий лічильник насичення правильно передбачить гілку, за винятком кількох ітерацій після того, як вона змінить напрямок.
Швидка візуалізація:
T = взята гілка
N = гілка не взята
дані [] = 0, 1, 2, 3, 4, ... 126, 127, 128, 129, 130, ... 250, 251, 252, ...
галузь = N N N N N ... N N T T T ... T T T ...
= NNNNNNNNNNNN ... NNNNNNNTTTTTTTTT ... TTTTTTTTTT (легко передбачити)
Однак, коли дані повністю випадкові, предиктор гілки стає марним, оскільки він не може передбачити випадкові дані. Таким чином, ймовірно, буде близько 50% непередбачуваних випадків (не краще, ніж випадкові вгадування).
дані [] = 226, 185, 125, 158, 198, 144, 217, 79, 202, 118, 14, 150, 177, 182, 133, ...
відгалуження = T, T, N, T, T, T, T, N, T, N, N, T, T, T, N ...
= TTNTTTTNTNNTTTN ... (абсолютно випадково - важко передбачити)
То що можна зробити?
Якщо компілятор не може оптимізувати гілку в умовний хід, ви можете спробувати кілька хакерів, якщо ви готові пожертвувати читабельністю для продуктивності.
Замінити:
якщо (дані [c]> = 128)
сума + = дані [c];
з:
int t = (дані [c] - 128) >> 31;
сума + = ~ t & дані [c];
Це усуває гілку і замінює її деякими побітовими операціями.
(Зверніть увагу, що цей злом не є суто еквівалентним оригінальному оператору if. Але в цьому випадку він діє для всіх вхідних значень даних [].)
Тести: Core i7 920 на 3,5 ГГц
C ++ - Visual Studio 2010 - випуск x64
// Відділення - Випадкове
секунд = 11,777
// Гілка - відсортовано
секунд = 2,352
// Без гілок - Випадковий
секунд = 2,564
// Без гілок - відсортовано
секунд = 2,587
Java - NetBeans 7.1.1 JDK 7 - x64
// Відділення - Випадкове
секунд = 10,93293813
// Гілка - відсортовано
секунд = 5,643797077
// Без гілок -Випадкові
секунд = 3.113581453
// Без гілок - відсортовано
секунд = 3,186068823
Спостереження:
З відділенням: Існує величезна різниця між відсортованими та невідсортованими даними.
За допомогою Hack: немає різниці між відсортованими та невідсортованими даними.
У випадку C ++ хак насправді трохи повільніший, ніж у гілці, коли дані сортуються.
Загальне правило - уникати розгалуження, залежного від даних, у критичних циклах (наприклад, у цьому прикладі).
Оновлення:
GCC 4.6.1 з -O3 або -ftree-vectorize на x64 може генерувати умовний хід. Тож немає різниці між відсортованими та невідсортованими даними - обидва швидкі.
(Або дещо швидше: для вже відсортованого випадку cmov може бути повільнішим, особливо якщо GCC ставить його на критичний шлях, а не просто додає, особливо в Intel перед Бродвеллом, де cmov має латентність у 2 цикли: прапор оптимізації gcc -O3 робить код повільнішим ніж -O2)
VC ++ 2010 не може генерувати умовні переміщення для цієї гілки навіть під / Ox.
Компілятор Intel C ++ (ICC) 11 робить щось дивовижне. Він обмінюється двома петлями, піднімаючи тим самим непередбачувану гілку до зовнішньої петлі. Отже, він не тільки захищений від непередбачуваних прогнозів, але і вдвічі швидший за те, що може створити VC ++ та GCC! Іншими словами, ICC скористався тестовим циклом, щоб перемогти еталон ...
Якщо ви даєте компілятору Intel код без гілок, він просто векторизує його ... і такий же швидкий, як і з гілкою (із циклічним обміном).
Це свідчить про те, що навіть зрілі сучасні компілятори можуть дико відрізнятися в своїх можливостях оптимізувати код ...
|
Прогнозування галузей.
У відсортованому масиві умова data [c]> = 128 спочатку є хибною для ряду значень, потім стає істинною для всіх наступних значень. Це легко передбачити. За допомогою несортованого масиву ви платите за вартість розгалуження.
|
Причиною того, що продуктивність різко покращується при сортуванні даних, є те, що штраф за передбачення гілок видаляється, як це прекрасно пояснюється у відповіді Mysticial.
Тепер, якщо ми подивимось на код
якщо (дані [c]> = 128)
сума + = дані [c];
ми можемо виявити, що значення цієї конкретної гілки if ... else ... полягає в додаванні чогось, коли умова виконана. Цей тип гілки можна легко перетворити в умовний оператор переміщення, який буде скомпільований в умовну інструкцію переміщення: cmovl, в системі x86. Гілка і, таким чином, потенційне покарання за прогнозування гілки видаляється.
У C, отже, C ++, оператор, який буде компілювати безпосередньо (без будь-якої оптимізації) в інструкцію умовного переміщення в x86, є потрійним оператором ...? ...: .... Отже, ми переписуємо наведене вище твердження в еквівалент:
сума + = дані [c]> = 128? дані [c]: 0;
Зберігаючи читабельність, ми можемо перевірити коефіцієнт прискорення.
На Intel Core i7-2600K @ 3,4 ГГц та режимі випуску Visual Studio 2010 орієнтиром є (формат скопійований з Mysticial):
x86
// Відділення - Випадкове
секунд = 8,885
// Гілка - відсортовано
секунд = 1,528
// Без гілок - Випадковий
секунд = 3,716
// Без гілок - відсортовано
секунди = 3,71
x64
// Відділення - Випадкове
секунд = 11.302
// Гілка - відсортовано
секунд = 1,830
// Без гілок - Випадковий
секунд = 2,736
// Без гілок - відсортовано
секунд = 2,737
Результат надійний під час кількох тестів. Ми отримуємо велике прискорення, коли результат розгалуження непередбачуваний, але ми трохи страждаємо, коли він передбачуваний. Насправді при використанні умовного переміщення продуктивність однакова незалежно від шаблону даних.
А тепер давайте розглянемо уважніше, досліджуючи збірку x86, яку вони генерують. Для простоти ми використовуємо дві функції max1 та max2.
max1 використовує умовну гілку, якщо ... ще ...:
int max1 (int a, int b) {
якщо (a> b)
повернути a;
ще
повернення b;
}
max2 використовує тернарний оператор ...? ...: ...:
int max2 (int a, int b) {
повернути a> b? a: b;
}
На машині x86-64 GCC -S генерує збірку нижче.
: max1
movl% edi, -4 (% rbp)
movl% esi, -8 (% rbp)
movl -4 (% rbp),% eax
cmpl -8 (% rbp),% eax
jle .L2
movl -4 (% rbp),% eax
movl% eax, -12 (% rbp)
jmp .L4
.L2:
movl -8 (% rbp),% eax
movl% eax, -12 (% rbp)
.L4:
movl -12 (% rbp),% eax
залишати
відступ
: max2
movl% edi, -4 (% rbp)
movl% esi, -8 (% rbp)
movl -4 (% rbp),% eax
cmpl% eax, -8 (% rbp)
cmovge -8 (% rbp),% eax
залишати
відступ
max2 використовує набагато менше коду через використання інструкції cmovge. Але справжній виграш полягає в тому, що max2 не передбачає стрибків гілок, jmp, які мали б суттєві покарання за продуктивність, якщо прогнозований результат буде неправильним.
То чому умовний хід працює краще?
У типовому процесорі x86 виконання команди ділиться на кілька етапів. Грубо кажучи, у нас є різне обладнання, щоб мати справу з різними етапами. Тому нам не потрібно чекати закінчення однієї інструкції, щоб розпочати нову. Це називається конвеєром.
У випадку розгалуження наступна інструкція визначається попередньою, тому ми не можемо виконати конвеєризацію. Ми повинні або почекати, або передбачити.
У випадку умовного переміщення,інструкція умовного переміщення виконання поділяється на кілька етапів, але більш ранні етапи, такі як Fetch та Decode, не залежать від результату попередньої інструкції; лише останні етапи потребують результату. Таким чином, ми чекаємо частки часу виконання однієї інструкції. Ось чому версія умовного переміщення є повільнішою, ніж гілка, коли прогнозування є простим.
Книга "Комп'ютерні системи: перспектива програміста", друге видання, детально пояснює це. Ви можете перевірити Розділ 3.6.6 Інструкцій з умовного переміщення, цілий розділ 4 - Архітектура процесора та Розділ 5.11.2 - Спеціальний режим щодо покарання за прогнозування та непередбачення прогнозів.
Іноді деякі сучасні компілятори можуть оптимізувати наш код до збірки з кращою продуктивністю, іноді деякі компілятори не можуть (у коді, про який йде мова, використовується власний компілятор Visual Studio). Знання різниці в продуктивності між гілкою та умовним переміщенням, коли непередбачувано, може допомогти нам написати код з кращою продуктивністю, коли сценарій стає настільки складним, що компілятор не може оптимізувати їх автоматично.
|
Якщо вам цікаво ще більше оптимізацій, які можна зробити для цього коду, розгляньте це:
Починаючи з вихідного циклу:
для (без знака i = 0; i <100000; ++ i)
{
для (без підпису j = 0; j  = 128)
сума + = дані [j];
}
}
За допомогою циклічного обміну ми можемо безпечно змінити цей цикл на:
для (без підпису j = 0; j  = 128)
сума + = дані [j];
}
}
Потім ви можете бачити, що умовний if постійний протягом усього виконання циклу i, тому ви можете підняти if out:
для (без підпису j = 0; j  = 128)
{
для (без знака i = 0; i <100000; ++ i)
{
сума + = дані [j];
}
}
}
Потім ви бачите, що внутрішній цикл можна згорнути в один єдиний вираз, припускаючи, що модель з плаваючою точкою дозволяє це (наприклад, / fp: швидкий)
для (без підпису j = 0; j  = 128)
{
сума + = дані [j] * 100000;
}
}
Це в 100 000 разів швидше, ніж раніше.
|
Без сумніву, деяких з нас зацікавлять способи ідентифікації коду, який є проблематичним для прогнозування гілок ЦП. Інструмент Valgrind cachegrind має симулятор передбачення гілок, увімкнений за допомогою прапора --branch-sim = yes. Запуск його на прикладах у цьому питанні, з кількістю зовнішніх циклів, зменшених до 10000 і зібраних з g ++, дає такі результати:
Відсортовано:
== 32551 == Філії: 656 645 130 (656 609 208 умовно + 35 922 інд)
== 32551 == Непередбачувані прогнози: 169 556 (169 095 умовних + 461 інд)
== 32551 == Частота помилок: 0,0% (0,0% + 1,2%)
Несортоване:
== 32555 == Відділення: 655 996 082 (655960160 умовно + 35922 інд)
== 32555 == Непередбачувані прогнози: 164 073 152 (164 072 692 умовно + 460 інд)
== 32555 == Частота помилок: 25,0% (25,0% + 1,2%)
Переходячи до рядкового виводу, виробленого cg_annotate, ми бачимо для відповідного циклу:
Відсортовано:
Bc Bcm Bi Bim
10 001 4 0 0 для (без знака i = 0; i <10000; ++ i)
. . . . {
. . . . // первинний цикл
327 690 000 10 016 0 0 для (без підпису c = 0; c  = 128)
0 0 0 0 сума + = дані [c];
. . . . }
. . . . }
Несортоване:
Bc Bcm Bi Bim
10 001 4 0 0 для (без знака i = 0; i <10000; ++ i)
. . . . {
. . . . // первинний цикл
327 690 000 10 038 0 0 для (без підпису c = 0; c  = 128)
0 0 0 0 сума + = дані [c];
. . . . }
. . . . }
Це дозволяє легко визначити проблемний рядок - у несортованій версії рядок if (data [c]> = 128) спричиняє 164 050 007 неправильно передбачених умовних гілок (Bcm) за моделлю прогнозування гілок cachegrind, тоді як у відсортованій версії це лише 10 006 .
Крім того, в Linux ви можете використовувати підсистему лічильників продуктивності для виконання того самого завдання, але з власною продуктивністю за допомогою лічильників процесора.
перф. статистика. / найсумнішіше_сортування
Відсортовано:
Статистика лічильника продуктивності для './sumtest_sorted':
11808.095776 годинник завдань # 0.998 Використані процесори
1062 перемикачів контексту # 0,090 К / с
14 міграцій процесора # 0,001 К / с
337 помилок сторінки # 0,029 К / с
26 487 882 764 тактів # 2.243 ГГц
41 025 654 322 інструкцій # 1,55 Insns за цикл
65588713779 гілок # 555.455 М / с
567 204 пропусків філій # 0,01% усіх філій
Минуло 11,827228330 секунд
Несортоване:
Продуктивністьстатистика лічильника для './sumtest_unsorted':
28877.954344 годинник завдань # 0.998 Використані процесори
2584 контекстних перемикачів # 0,089 К / с
18 міграцій процесора # 0,001 К / с
335 помилок сторінки # 0,012 К / с
65 076 127 275 циклів # 2.253 ГГц
41 032 528 741 інструкція # 0,63 Insns за цикл
6,560,579,013 гілок # 227,183 М / с
1646 394 749 пропусків філій # 25,10% усіх філій
Минуло 28,935500947 секунд
Він також може робити анотацію вихідного коду з розбиранням.
запис перфомансу -e гілка-промах ./sumtest_unsorted
perf примітка -d sumtest_unsorted
Відсоток | Вихідний код та розбирання sumtest_unsorted
------------------------------------------------
...
: сума + = дані [c];
0,00: 400a1a: mov -0x14 (% rbp),% eax
39,97: 400a1d: mov% eax,% eax
5.31: 400a1f: mov -0x20040 (% rbp,% rax, 4),% eax
4,60: 400a26: cltq
0,00: 400a28: додайте% rax, -0x30 (% rbp)
...
Докладніше див. У підручнику з продуктивності.
|
Я просто прочитав це питання та відповіді на нього, і відчуваю, що відповіді бракує.
Поширеним способом усунення передбачення гілок, який, як мені здається, працює особливо добре в керованих мовах, є пошук таблиці замість використання гілки (хоча я не тестував його в цьому випадку).
Цей підхід працює загалом, якщо:
це невелика таблиця, яка, швидше за все, буде кешована в процесорі, і
ви запускаєте речі в досить щільному циклі, і / або процесор може попередньо завантажити дані.
Передумови і чому
З точки зору процесора, ваша пам’ять працює повільно. Щоб компенсувати різницю в швидкості, у ваш процесор вбудовано пару кеш-пам’яті (кеш L1 / L2). Тож уявіть, що ви робите свої приємні розрахунки і з’ясуєте, що вам потрібен шматочок пам’яті. Процесор отримає операцію `` завантаження '' і завантажить частину пам'яті в кеш - а потім використовує кеш для решти обчислень. Оскільки пам’ять відносно повільна, це „завантаження” сповільнить вашу програму.
Як і передбачення гілок, це було оптимізовано в процесорах Pentium: процесор передбачає, що йому потрібно завантажити фрагмент даних, і намагається завантажити його в кеш, перш ніж операція фактично потрапить у кеш. Як ми вже бачили, прогнозування гілок іноді стає жахливо неправильним - у найгіршому випадку вам потрібно повернутися назад і насправді чекати завантаження пам'яті, яке триватиме вічно (іншими словами: невдале прогнозування гілок - це погано, завантаження після помилки передбачення гілки просто жахливо!).
На наше щастя, якщо шаблон доступу до пам'яті передбачуваний, процесор завантажить його у свій швидкий кеш, і все добре.
Перше, що нам потрібно знати, це те, що мало? Хоча, як правило, краще менше, меншим правилом є дотримання таблиць підстановки розміром <= 4096 байт. Як верхню межу: якщо ваша таблиця пошуку перевищує 64 КБ, можливо, варто переглянути її.
Побудова таблиці
Отже, ми з’ясували, що можемо створити невеликий стіл. Наступне, що потрібно зробити, це отримати функцію пошуку на місці. Функції пошуку - це, як правило, невеликі функції, які використовують пару основних цілочисельних операцій (і, або, xor, зміщують, додають, видаляють і, можливо, множать). Ви хочете, щоб ваш ввід переводився функцією пошуку в якийсь «унікальний ключ» у вашій таблиці, який потім просто дає вам відповідь на всю роботу, яку ви хотіли зробити.
У цьому випадку:> = 128 означає, що ми можемо зберегти значення, <128 означає, що ми позбулися його. Найпростіший спосіб це зробити, використовуючи "І": якщо ми зберігаємо його, ми І це за допомогою 7FFFFFFF; якщо ми хочемо позбутися цього, ми І це з 0. Зверніть увагу також, що 128 - це степеня 2 - тому ми можемо продовжувати і складати таблицю з 32768/128 цілими числами і заповнювати її нулем і великою кількістю 7FFFFFFFF.
Керовані мови
Ви можете здивуватися, чому це добре працює на керованих мовах. Врешті-решт, керовані мови перевіряють межі масивів гілкою, щоб перешкодити вам ...
Ну не зовсім ... :-)
Проведено досить багато робіт з усунення цієї галузі для керованих мов. Наприклад:
for (int i = 0; i  = 128)? c: 0;
}
// Тест
DateTime startTime = System.DateTime.Now;
довга сума = 0;
для (int i = 0; i <100000; ++ i)
{
// Первинний цикл
для (int j = 0; j  = 128. Це означає, що ми можемо легко витягти один біт, який скаже нам, чи хочемо ми значення, чи ні: шляхом зміщення дані вправо на 7 біт, нам залишається 0 біт або 1 біт, і ми хочемо додати значення лише тоді, коли у нас є 1 біт. Давайте назвемо цей біт "бітом рішення".
Використовуючи значення 0/1 біта рішення як індекс масиву, ми можемо створити код, який буде однаково швидким незалежно від того, відсортовано дані чи ні. Наш код завжди додасть значення, але коли біт рішення дорівнює 0, ми додамо значення десь, що нас не хвилює. Ось код:
// Тест
clock_t start = clock ();
довгий довгий a [] = {0, 0};
довга довга сума;
для (без знака i = 0; i <100000; ++ i)
{
// Первинний цикл
для (без підпису c = 0; c > 7);
a [j] + = дані [c];
}
}
double elapsedTime = static_cast  (clock () - start) / CLOCKS_PER_SEC;
сума = a [1];
Цей код витрачає половину додань, але ніколи не має помилки передбачення гілки. Це набагато швидше на випадкових даних, ніж версія з фактичним оператором if.
Але під час мого тестування явна таблиця пошуку була трохи швидшою, ніж це, можливо, тому, що індексація в таблиці пошуку була трохи швидшою, ніж зміщення бітів. Це показує, як мій код налаштовує та використовує пошукову таблицю (у коді незвично називається lut для "LookUp Table"). Ось код С ++:
// Оголосіть, а потім заповніть таблицю пошуку
int lut [256];
для (без знака c = 0; c <256; ++ c)
lut [c] = (c> = 128)? c: 0;
// Використовуйте таблицю пошуку після її побудови
для (без знака i = 0; i <100000; ++ i)
{
// Первинний цикл
для (без підпису c = 0; c )
node = node-> pLeft;
ще
node = node-> pRight;
ця бібліотека зробить щось на зразок:
i = (значення x );
вузол = вузол-> посилання [i];
Ось посилання на цей код: Червоні чорні дерева, вічно спантеличені
|
У відсортованому випадку ви можете зробити краще, ніж покладатися на успішне передбачення гілок або будь-який трюк порівняння без гілок: повністю видаліть гілку.
Дійсно, масив розділений на суміжну зону з даними <128, а інший з даними> = 128. Отже, слід знайти точку розділу за допомогою дихотомічного пошуку (використовуючи порівняння Lg (arraySize) = 15), а потім зробити пряме накопичення з цей момент.
Щось на зразок (не позначено)
int i = 0, j, k = arraySize;
в той час як (i > 1;
якщо (дані [j]> = 128)
k = j;
ще
i = j;
}
сума = 0;
для (; i > 1;
для (i = 0, k = arraySize; i  = 128? k: i) = j)
j = (i + k) >> 1;
для (сума = 0; i  = 128)
/ \
/ \
/ \
true / \ false
/ \
/ \
/ \
/ \
Б) сума + = дані [c]; C) для циклу або друку ().
Без прогнозування гілок могло б статися таке:
Щоб виконати інструкцію B або інструкцію C, процесору доведеться почекати, поки інструкція A не дійде до етапу EX у конвеєрі, оскільки рішення про перехід до інструкції B або інструкції C залежить від результату інструкції A. Отже, конвеєр буде виглядати так.
коли якщо умова повертає true:
Коли якщо умова повертає false:
В результаті очікування результату вказівки А, загальний цикл процесора, витрачений у вищезазначеному випадку (без передбачення гілки; як для істинного, так і для хибного), дорівнює 7.
То що таке прогнозування галузей?
Прогнозувач гілок спробує вгадати, яким шляхом піде гілка (структура if-then-else), перш ніж це буде відомо точно. Він не буде чекати, поки інструкція А дійде до стадії EX трубопроводу, але він вгадає рішення і перейде до цієї інструкції (B або C у випадку нашого прикладу).
У разі правильного припущення конвеєр виглядає приблизно так:
Якщо пізніше виявиться, що припущення було помилковим, частково виконані інструкції відкидаються, а конвеєр починається спочатку з правильної гілки, що спричиняє затримку.
Час, який витрачається на випадок неправильного передбачення гілки, дорівнює кількості етапів у конвеєрі від етапу отримання до етапу виконання. Сучасні мікропроцесори, як правило, мають досить довгі трубопроводи, так що затримка непередбачуваності становить від 10 до 20 тактових циклів. Чим довший трубопровід, тим більша потреба в хорошому прогнозі відгалуження.
У коді OP перший раз, коли умовний предиктор гілки не має жодної інформації для підґрунтування передбачення, тому перший раз він випадково вибере наступну інструкцію. Пізніше у циклі for він може базувати прогноз на історії.
Для масиву, відсортованого за зростанням, є три можливості:
Усі елементи менше 128
Усі елементи перевищують 128
Деякі початкові нові елементи мають менше 128, а пізніше вони перевищують 128
Припустимо, що предиктор завжди прийматиме справжню гілку при першому запуску.
Отже, у першому випадку це завжди буде приймати істинугалузь, оскільки історично всі її прогнози правильні.
У 2-му випадку спочатку він буде прогнозувати неправильно, але через кілька ітерацій прогнозуватиме правильно.
У 3-му випадку він спочатку буде правильно прогнозувати, поки елементи не стануть меншими ніж 128. Після чого він деякий час зазнає невдачі, а сам виправиться, коли побачить помилку передбачення гілок в історії.
У всіх цих випадках збій буде занадто меншим за кількістю, і, як результат, лише кілька разів йому потрібно буде відкинути частково виконані інструкції і почати спочатку з правильної гілки, що призведе до меншої кількості циклів процесора.
Але у випадку випадкового невідсортованого масиву, передбачення потрібно буде відкинути частково виконані інструкції і почати спочатку з правильної гілки більшу частину часу, що призведе до більшої кількості циклів процесора порівняно з відсортованим масивом.
|
Офіційна відповідь буде від
Intel - уникнення витрат на непередбачення гілок
Intel - реорганізація філій та циклів для запобігання непередбачуваним прогнозам
Наукові праці - галузева архітектура прогнозування комп'ютерів
Книги: J.L.Hennessy, D.A. Паттерсон: Комп’ютерна архітектура: кількісний підхід
Статті в наукових публікаціях: Т.Й. Так, Ю.Н. Патт зробив багато з них на прогнози галузей.
З цієї чудової схеми ви також можете зрозуміти, чому передбачувач гілок заплутається.
Кожен елемент у вихідному коді є випадковим значенням
дані [c] = std :: rand ()% 256;
отже, предиктор змінить сторону під час удару std :: rand ().
З іншого боку, як тільки сортується, предиктор спочатку переходить у стан сильно не прийнятих, і коли значення змінюються на високі значення, предиктор протягом трьох прогонів змінюватиметься від сильно не прийнятого до сильно прийнятого.
|
У цьому ж рядку (я думаю, що це не було виділено жодною відповіддю), добре згадати, що іноді (особливо в програмному забезпеченні, де продуктивність має значення - як у ядрі Linux), ви можете знайти такі твердження if, як наведене нижче:
if (ймовірно (everything_is_ok))
{
/* Робити щось */
}
або подібним чином:
якщо (малоймовірно (дуже_імовірний_ стан))
{
/* Робити щось */
}
І вірогідні (), і малоймовірні () насправді є макросами, які визначаються за допомогою чогось на зразок __builtin_expect GCC, щоб допомогти компілятору вставити код прогнозування на користь умови з урахуванням інформації, наданої користувачем. GCC підтримує інші вбудовані модулі, які можуть змінити поведінку запущеної програми або видати інструкції низького рівня, такі як очищення кеш-пам'яті тощо. Див. Цю документацію, яка розглядає доступні вбудовані GCC.
Зазвичай такий тип оптимізації в основному зустрічається в додатках у реальному часі або вбудованих системах, де час виконання має важливе значення і є критичним. Наприклад, якщо ви перевіряєте наявність якоїсь помилки, яка трапляється лише 1/10000000 разів, то чому б не повідомити про це компілятор? Таким чином, за замовчуванням передбачення гілки передбачає помилкову умову.
|
Логічні операції, що часто використовуються в C ++, створюють багато гілок у складеній програмі. Якщо ці гілки знаходяться всередині петель і їх важко передбачити, вони можуть значно уповільнити виконання. Логічні змінні зберігаються як 8-бітові цілі числа зі значенням 0 для false і 1 для true.
Булеві змінні перевизначені в тому сенсі, що всі оператори, які мають в якості вхідних даних булеві змінні, перевіряють, чи мають входи будь-яке інше значення, ніж 0 або 1, але оператори, які мають булеві значення як вихід, не можуть виробляти іншого значення, ніж 0 або 1. Це робить операції Логічні змінні як вхідні дані менш ефективні, ніж потрібно.
Розглянемо приклад:
bool a, b, c, d;
c = a && b;
d = a || б;
Зазвичай це реалізується компілятором наступним чином:
bool a, b, c, d;
якщо (a! = 0) {
якщо (b! = 0) {
c = 1;
}
ще {
перейти до CFALSE;
}
}
ще {
CFALSE:
c = 0;
}
якщо (a == 0) {
якщо (b == 0) {
d = 0;
}
ще {
перейти до DTRUE;
}
}
ще {
DTRUE:
d = 1;
}
Цей код далеко не оптимальний. Гілки можуть зайняти багато часу у випадку непередбачуваних прогнозів. Булеві операції можна зробити набагато ефективнішими, якщо з упевненістю відомо, що операнди не мають інших значень, окрім 0 та 1. Причина, чому компілятор не робить такого припущення, полягає в тому, що змінні можуть мати інші значення, якщо вони неініціалізовані або походять з невідомих джерел. Вищезазначений код можна оптимізувати, якщо a та b були ініціалізовані для дійсних значень або якщо вони надходять від операторів, які видають булевий вивід. Оптимізований код виглядає так:
char a = 0, b = 1, c, d;
c = a & b;
d = a | б;
char використовується замість bool, щоб зробити можливим використання побітових операторів (& та |) замість булевих операторів (&& та ||). Побітові оператори - це окремі інструкції, які займають лише один тактовий цикл. Оператор АБО (|) працює, навіть якщо значення a та b мають інші значення, ніж 0 або 1. Оператор AND (&) та оператор EXCLUSIVE OR (^) можуть давати суперечливі результати, якщо операнди мають інші значення, ніж 0 та 1.
~ не можна використовувати для НЕ. Натомість,ви можете зробити логічне значення НЕ для змінної, яка, як відомо, дорівнює 0 або 1, XOR'ом з 1:
bool a, b;
b =! a;
може бути оптимізовано для:
char a = 0, b;
b = a ^ 1;
a && b не можна замінити на a & b, якщо b - вираз, який не слід обчислювати, якщо a хибне (&& не буде оцінювати b, & will). Так само, a || b не можна замінити на | b, якщо b - вираз, який не слід обчислювати, якщо a відповідає істині.
Використання побітових операторів вигідніше, якщо операнди є змінними, ніж якщо операнди є порівняннями:
bool a; подвійний x, y, z;
a = x> y && z <5,0;
є оптимальним у більшості випадків (якщо ви не очікуєте, що вираз && генерує багато непередбачуваних гілок).
|
Це точно!...
Прогнозування розгалужень призводить до того, що логіка працює повільніше через перемикання, яке відбувається у вашому коді! Це все одно, що ви їдете прямою вулицею чи вулицею з великою кількістю поворотів, точно пряму потрібно зробити швидше! ...
Якщо масив відсортовано, на першому кроці ваша умова хибна: data [c]> = 128, а потім стає справжнім значенням на всьому шляху до кінця вулиці. Ось так ви швидше досягаєте кінця логіки. З іншого боку, використовуючи невідсортований масив, вам потрібно багато перетворювати та обробляти, що напевно робить ваш код повільнішим ...
Подивіться на зображення, яке я створив для вас нижче. Яку вулицю збираються закінчити швидше?
Тож програмно передбачення гілок спричиняє повільніший процес ...
Також наприкінці, добре знати, що у нас є два типи передбачень гілок, кожна з яких впливатиме на ваш код по-різному:
1. Статичні
2. Динамічний
Статичне передбачення гілок використовується мікропроцесором вперше
зустрічається умовна гілка, а динамічне передбачення гілки -
використовується для успішного виконання умовного коду гілки.
Для того, щоб ефективно написати свій код, скористайтеся ними
правила, коли пишеш if-else або перемикає оператори, перевіряй найбільше
спочатку поширені випадки, і поступово працюйте до найменш поширених.
Цикли не обов'язково вимагають особливого впорядкування коду для
статичне передбачення гілки, як лише умова ітератора циклу
зазвичай використовується.
|
На це питання вже багато разів давали чудові відповіді. Проте я хотів би звернути увагу групи на ще один цікавий аналіз.
Нещодавно цей приклад (модифікований дуже незначно) також використовувався як спосіб продемонструвати, як фрагмент коду може бути профільований у самій програмі на Windows. Попутно автор також показує, як використовувати результати, щоб визначити, де код проводить більшу частину часу як у відсортованому, так і в невідсортованому випадку. Нарешті, стаття також показує, як використовувати маловідому особливість HAL (апаратного рівня абстракції), щоб визначити, наскільки велике непередбачення гілок відбувається у невідсортованому випадку.
Посилання тут:
Демонстрація самопрофілювання
|
Як і те, про що вже згадували інші, за таємницею стоїть передбачувач галузі.
Я не намагаюся щось додати, а пояснити концепцію по-іншому.
У вікі є короткий вступ, який містить текст та схему.
Мені подобається пояснення нижче, яке використовує діаграму для інтуїтивного опрацювання передбачувача галузі.
У комп’ютерній архітектурі прогнозом галузей є a
цифрова схема, яка намагається вгадати, в який бік гілка (наприклад
if-then-else структура) піде до того, як це точно відомо.
Призначення гілки прогнозування полягає в поліпшенні потоку в
інструкція конвеєра. Провідники галузей відіграють вирішальну роль у
досягнення високих ефективних характеристик у багатьох сучасних конвеєрних системах
мікропроцесорні архітектури, такі як x86.
Двостороннє розгалуження зазвичай реалізується з умовним стрибком
інструкція. Умовний стрибок можна або «не взяти», і продовжити
виконання з першою гілкою коду, яка слід негайно
після умовного стрибка, або його можна "взяти" і перейти до a
інше місце в пам'яті програм, де знаходиться друга гілка коду
зберігається. Достеменно невідомо, чи буде умовний стрибок
прийнято чи не прийнято до обчислення стану та
умовний стрибок пройшов етап виконання в інструкції
трубопроводу (див. рис. 1).
Виходячи з описаного сценарію, я написав демонстрацію анімації, щоб показати, як виконуються інструкції в конвеєрі в різних ситуаціях.
Без передбачувача галузі.
Без прогнозування гілок процесору доведеться чекати, поки
вказівка ​​умовного стрибка пройшла етап виконання перед
наступна інструкція може перейти до етапу завантаження в конвеєр.
Приклад містить три інструкції, а перша - умовна інструкція переходу. Останні дві інструкції можуть надходити в конвеєр, доки не буде виконана інструкція умовного переходу.
Потрібно 9 тактових циклів, щоб виконати 3 інструкції.
Використовуйте Branch Predictor і не робіть умовного стрибка. Припустимо, що прогноз не приймаєумовний стрибок.
Потрібно 7 тактових циклів, щоб виконати 3 інструкції.
Використовуйте Branch Predictor і виконайте умовний стрибок. Припустимо, що прогноз не виконує умовного стрибка.
Потрібно 9 тактових циклів, щоб виконати 3 інструкції.
Час, який витрачається на випадок непередбачення гілки, дорівнює
кількість етапів у трубопроводі від етапу вибору до
виконати етап. Сучасні мікропроцесори мають, як правило, досить довгі
трубопроводів, так що затримка непередбачуваного повідомлення становить від 10 до 20 годин
циклів. Як результат, збільшення довжини трубопроводу збільшує потребу в
вдосконалений прогноз гілок.
Як бачите, схоже, у нас немає причин не використовувати Branch Predictor.
Це досить проста демонстрація, яка роз'яснює саму основну частину Branch Predictor. Якщо ці GIF-файти дратують, будь ласка, не соромтеся видаляти їх із відповіді, і відвідувачі також можуть отримати вихідний демо-код із BranchPredictorDemo
|
Приріст прогнозування галузі!
Важливо розуміти, що непередбачення гілок не уповільнює програми. Вартість пропущеного передбачення така, ніби передбачення гілки не існувало, і ви чекали, коли оцінка виразу вирішить, який код запускати (подальше пояснення в наступному абзаці).
якщо (вираз)
{
// Запуск 1
} ще {
// Запуск 2
}
Всякий раз, коли є оператор if-else \ switch, вираз повинен бути оцінений, щоб визначити, який блок слід виконати. У коді збірки, сформованому компілятором, вставляються вказівки умовної гілки.
Інструкція з розгалуження може призвести до того, що комп'ютер почне виконувати іншу послідовність команд і, таким чином, відхилятиметься від поведінки за замовчуванням при виконанні інструкцій в порядку (тобто якщо вираз хибний, програма пропускає код блоку if) залежно від якоїсь умови, яка - це вираз оцінки в нашому випадку.
З огляду на це, компілятор намагається передбачити результат до того, як його фактично оцінити. Він отримає вказівки з блоку if, і якщо вираз виявиться правдивим, тоді чудово! Ми виграли час, необхідний для його оцінки, і досягли прогресу в коді; якщо ні, тоді ми запускаємо неправильний код, конвеєр очищається і запускається правильний блок.
Візуалізація:
Скажімо, вам потрібно вибрати маршрут 1 або маршрут 2. Чекаючи, поки ваш партнер перевірить карту, ви зупинились на ## і чекали, або ви можете просто вибрати маршрут1, і якщо вам пощастило (маршрут 1 - правильний маршрут), тоді чудово, що вам не потрібно було чекати, поки ваш партнер перевірить карту (ви заощадили час, який йому знадобився б для перевірки карти), інакше ви просто повернетесь назад.
Незважаючи на те, що промивка трубопроводів відбувається дуже швидко, сьогодні прийняти цю гру варто того. Передбачити відсортовані дані або дані, які змінюються повільно, завжди простіше і краще, ніж передбачити швидкі зміни.
O Маршрут 1 / -------------------------------
/ | \ /
| --------- ## /
/ \ \
\
Маршрут 2 \ --------------------------------
|
На ARM не потрібна гілка, оскільки кожна інструкція має 4-бітове поле умови, яке тестує (за нульової вартості) будь-яке з 16 різних різних умов, які можуть виникнути в Реєстрі стану процесора, і якщо умовою інструкції є false, інструкція пропущена. Це виключає необхідність у коротких гілках, і для цього алгоритму не було б передбачення гілок. Отже, відсортована версія цього алгоритму буде працювати повільніше, ніж невідсортована версія на ARM, через додаткові накладні витрати на сортування.
Внутрішній цикл для цього алгоритму виглядатиме приблизно так у мові асемблера ARM:
MOV R0, # 0 // R0 = сума = 0
MOV R1, # 0 // R1 = c = 0
ADR R2, дані // R2 = адреса масиву даних (помістіть цю інструкцію поза зовнішнього циклу)
.inner_loop // Мітка розгалуження внутрішнього циклу
LDRB R3, [R2, R1] // R3 = дані [c]
CMP R3, # 128 // порівняємо R3 до 128
ДОДАТИ R0, R0, R3 // якщо R3> = 128, то сума + = дані [c] - гілка не потрібна!
ДОДАТИ R1, R1, # 1 // c ++
CMP R1, #arraySize // порівняємо c з arraySize
BLT inner_loop // Відгалуження до inner_loop, якщо c  ());
for (unsigned c = 0; c  = 128
сума = сума + дані1 (j);
кінець
кінець
кінець
toc;
ExeTimeWithSorting = toc - tic;
Результати для наведеного вище коду MATLAB такі:
a: Минулий час (без сортування) = 3479,880861 секунд.
b: Час, що минув (із сортуванням) = 2377,873098 секунд.
Результати коду С, як у @GManNickG, я отримую:
a: Минулий час (без сортування) = 19,8761 сек.
b: Час, що минув (із сортуванням) = 7,37778 сек.
Виходячи з цього, схоже, MATLAB майже в 175 разів повільніше, ніж реалізація C без сортування, і в 350 разів повільніше при сортуванні. Іншими словами, ефект (передбачення гілок) становить 1,46x для реалізації MATLAB та 2,7x для реалізації C.
|
В інших відповідях припущення, що потрібно сортувати дані, є неправильним.
Наступний код не сортує весь масив, а лише його 200-елементні сегменти, і таким чином працює найшвидше.
Сортування лише розділів k-елемента завершує попередню обробку за лінійний час, O (n), а не за час O (n.log (n)), необхідний для сортування всього масиву.
#include 
#include 
#include 
int main () {
дані int [32768]; const int l = розмір даних / розмір даних [0];
для (без знака c = 0; c  = 128)
сума + = дані [c];
}
}
std :: cout << static_cast  (clock () - start) / CLOCKS_PER_SEC << std :: endl;
std :: cout << "sum =" << sum << std :: endl;
}
Це також "доводить", що воно не має нічого спільного з будь-якими алгоритмічними проблемами, такими як порядок сортування, і це справді передбачення гілок.
|
Відповідь Бьярна Страуструпа на це питання:
Це звучить як запитання інтерв’ю. Це правда? Звідки ви знаєте? Погана ідея відповідати на питання щодо ефективності, не проводячи попередньо вимірювання, тому важливо знати, як вимірювати.
Отже, я спробував з вектором мільйона цілих чисел і отримав:
Вже відсортовано 32995 мілісекунд
Перемішано 125944 мілісекунди
Вже відсортовано 18610 мілісекунд
Перемішано 133304 мілісекунди
Вже відсортовано 17942 мілісекунд
Перемішано 107858 мілісекунд
Я пробіг це кілька разів, щоб бути впевненим. Так, явище справжнє. Моїм ключовим кодом було:
порожній запуск (вектор  & v, const string & label)
{
авто t0 = system_clock :: now ();
сортувати (v.begin (), v.end ());
auto t1 = system_clock :: now ();
cout << мітка
<< тривалість_запису <мікросекунди> (t1 - t0) .count ()
<< "мілісекунди \ n";
}
void tst ()
{
вектор  v (1'000'000);
iota (v.begin (), v.end (), 0);
run (v, "вже відсортовано");
std :: shuffle (v.begin (), v.end (), std :: mt19937 {std :: random_device {} ()});
запустити (v, "перетасовано");
}
Принаймні, явище справжнє з цим компілятором, стандартною бібліотекою та налаштуваннями оптимізатора. Різні варіанти реалізації можуть і дають різні відповіді. Насправді хтось проводив більш систематичне дослідження (швидкий веб-пошук це знайде), і більшість реалізацій показують цей ефект.
Однією з причин є передбачення гілок: ключовою операцією в алгоритмі сортування є “if (v [i]  = 128. Це означає, що ми можемо легко витягти один біт, який скаже нам, чи хочемо ми значення, чи ні: шляхом зміщення дані вправо на 7 біт, нам залишається 0 біт або 1 біт, і ми хочемо додати значення лише тоді, коли у нас є 1 біт. Давайте назвемо цей біт "бітом рішення".
Використовуючи значення 0/1 біта рішення як індекс масиву, ми можемо створити код, який буде однаково швидким незалежно від того, відсортовано дані чи ні. Наш код завжди додасть значення, але коли біт рішення дорівнює 0, ми додамо значення десь, що нас не хвилює. Ось код:
// Тест
clock_t start = clock ();
довгий довгий a [] = {0, 0};
довга довга сума;
для (без знака i = 0; i <100000; ++ i)
{
// Первинний цикл
для (без підпису c = 0; c > 7);
a [j] + = дані [c];
}
}
double elapsedTime = static_cast  (clock () - start) / CLOCKS_PER_SEC;
сума = a [1];
Цей код витрачає половину додань, але ніколи не має помилки передбачення гілки. Це набагато швидше на випадкових даних, ніж версія з фактичним оператором if.
Але під час мого тестування явна таблиця пошуку була трохи швидшою, ніж це, можливо, тому, що індексація в таблиці пошуку була трохи швидшою, ніж зміщення бітів. Це показує, як мій код налаштовує та використовує пошукову таблицю (у коді незвично називається lut для "LookUp Table"). Ось код С ++:
// Оголосіть, а потім заповніть таблицю пошуку
int lut [256];
для (без знака c = 0; c <256; ++ c)
lut [c] = (c> = 128)? c: 0;
// Використовуйте таблицю пошуку після її побудови
для (без знака i = 0; i <100000; ++ i)
{
// Первинний цикл
для (без підпису c = 0; c )
node = node-> pLeft;
ще
node = node-> pRight;
ця бібліотека зробить щось на зразок:
i = (значення x );
вузол = вузол-> посилання [i];
Це гарне рішення, і, можливо, воно спрацює.
|
Високоактивне запитання. Заробіть 10 репутації, щоб відповісти на це питання. Вимога про репутацію допомагає захистити це питання від спаму та відсутності відповідей.
Не відповідь, яку ви шукаєте? Перегляньте інші запитання, позначені тегом java c ++, оптимізація продуктивності, передбачення гілок або задайте власне запитання.